COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00013 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a32.tex[154,phy] \today\hfill}
\parskip 6pt

\bigskip
\line{\bf Equivalence and Minimization of Deterministic Finite Automata\hfill}

\smallskip
Let $Q$ be a set of deterministic finite
automaton states; they may belong to one or
to several automata, with a common alphabet~$\Sigma$. For $q\in Q$,
let $L↓q$ be the set of strings $\{\,x|q\delta↓x\in F\,\}$. Define 
$q↓1≡q↓2$ iff $L↓{q↓1}=L↓{q↓2}$; because $L↓q$ is a function of~$q$,
this is clearly an equivalence relation. Then $q↓1\not\equiv q↓2$ if
there is a string~$x$ for which $q↓1\delta↓x\in F$, $q↓2\delta↓x\not\in F$
(or vice versa). 

Define the relation $R↓i$ by:
$$\eqalign{R↓0&=F\times\bar{F}\cr
R↓{i+1}&=R↓i\cup\bigcup↓{a\in\Sigma}\delta↓a\circ R↓i\circ\delta↓a↑{-1}\,.\cr}$$
Because $R↓i$ is a non-decreasing subset of a domain of cardinality
$\left|Q\right|↑2$, it converges to a fixed relation~$R↓∞$ in at most
$\left|Q\right|↑2$ steps.

By induction, $qR↓iq'$ iff
$$(\exists x)(\left|x\right|≤i∧q\delta↓x\in F∧q'\delta↓x\in\bar{F})\,.$$

\medskip\noindent
Induction step:

\disleft 30pt:($\Rightarrow$):
Assume $qR↓{i+1}q'$, so either

\display 50pt:(1):
$qR↓iq'$, and by induction there is an $x$ of
length $≤i\ldots$, or

\display 50pt:(2):
$q\delta↓a\circ R↓i\circ\delta↓a↑{-1}q'$, so for some $q↓1$,
$q↓1'$, $q\delta↓aq↓1R↓iq↓1'\delta↓a↑{-1}q'$, and by induction there is an~$x$,
$\left|x\right|≤i$, for which $q↓1\delta↓x\in F$, $q↓1'\delta↓x\not\in F$, so
$q\delta↓{ax}\in F$, $q'\delta↓{ax}\not\in F$.

\disleft 30pt:($\Leftarrow$):
If there is an $x$ as described, and $\left|x\right|<i+1$, then by induction
$qR↓iq'$, so $qR↓{i+1}q'$. If $\left|x\right|=i+1$, then
$x=ay$ for some $a\in\Sigma$, and for some $q↓1$,~$q↓1'$,
$q\delta↓aq↓1$, $q↓1\delta↓y\in F$, $q'\delta↓aq↓1'$, $q↓1'\delta↓y\not\in F$, and
by induction $q↓1R↓iq↓1'$, so $q\delta↓aq↓1R↓iq↓1'\delta↓a↑{-1}q'$ and
$qR↓{i+1}q'$.

\smallskip
{\baselineskip 16pt
Since $R↓∞=\cup R↓i$, $qR↓∞q'$ iff $(\exists x)(q\delta↓x\in F∧q'\delta↓x\in\bar{F})$,
$q↓1\not\equiv q↓2$ iff $(q↓1R↓∞q↓2∨q↓2R↓∞q↓1)$, and the equivalence
relation~$R↓≡$ on states is $\overline{R↓∞\vphantom{↑1}}∧\overline{R↓∞↑{-1}}$.
(Alternatively, by letting $R↓0=F\times \overline{F}\cup \overline{F}\times F$,
we would have $R↓≡=\overline{R}↓∞$.
}

If $S$ is the start state of $M$ and $S'$ the start state of~$M'$,
$M≡M'$ iff $L↓M=L↓{M'}$ iff $L↓S=L↓{S'}$ iff $S\overline{R↓∞}S'$.
This provides an efficient test for equivalence of finite automata.

Given a finite automaton $M$, define $M↑{[\,]}$ in this way:
for $q\in Q↓M$, let $[q]$ be the equivalence class of~$q$, and
$Q↑{[\,]}=\{\,[q]\mid q\in Q\,\}$. Let
$\delta↓a↑{[\,]}$ be $\{\,([q↓1],[q↓2])\mid q↓1\delta↓aq↓2\,\}$.
Let $S↑{[\,]}=[S]$, $F↑{[\,]}=\hfil\break
\{\,[q]\mid q\in F\,\}$. We show
$M↑{[\,]}$ is a DFA and equivalent to~$M$. [RWF: rewrite the following]

\smallskip
\disleft 20pt:(1):
If $[q']\in F↑{[\,]}$, $q'≡q\in F$, $\epsilon\in L↓q=L↓{q'}$, and $q'\in F$.

\smallskip
\disleft 20pt:(2):
If $[q']\in S↑{[\,]}$, then $q'≡S$, $L↓{q'}=L↓S=L↓M$.

\smallskip
\disleft 20pt:(3):
If $q↓1\delta↓aq↓2$, $q↓1'\delta↓aq↓2'$, and $q↓1≡q↓1'$, then
$L↓{q↓1}=L↓{q↓i'}$, $\{\,x\mid ax\in L↓{q↓1}\,\}=\{\,x\mid ax\in L↓{q'↓1}\,\}$,
$L↓{q↓2}=L↓{q↓2'}$, so $q↓2≡q↓2'$. Therefore $[q↓1]\delta↓a↑{[\,]}=
\{\,q↓2'\mid q↓1≡q↓1'\delta↓aq↓2'\,\}=[q↓1\delta↓a]$ is singlevalued, so
$M↑{[\,]}$~is a~DFA.

\smallskip
\disleft 20pt:(4):
By induction on $\left|x\right|$, $q↓1\delta↓xq↓2$ implies 
$[q↓1]\delta↓x↑{[\,]}[q↓2]$.
Conversely, if $[q↓1]\delta↓x↑{[\,]}[q↓2]$, then
$q↓1\delta↓xq↓2'≡q↓2$. (Proof by reader.)

\smallskip
\disleft 20pt:(5):
$L↓M=L↓{M↑{[\,]}}$. If $x\in L↓M$, $S\delta↓xq\in F$, 
$[S]\delta↓x↑{[\,]}[q]\in F↑{[\,]}$,
$x\in L↓{M↑{[\,]}}$. Conversely, if $x\in L↓{M↑{[\,]}}$, 
$[S]\delta↓x↑{[\,]}[q]\in F↑{[\,]}$, $S\delta↓xq'≡q\in F$, $q'\in F$, 
and $x\in L↓M$.

\smallskip
We now show that $M↑{[\,]}$ is the minimum finite automaton equivalent
to~$M$. 

Let $M'$ be equivalent to~$M$, so $L↓{M'}=L↓M$. If $q↓1\not\equiv q↓2$,
$S\delta↓xq↓1$, $S\delta↓yq↓2$, then $\exists z$ such that $q↓1\delta↓z\in F$,
$q↓2z\in\bar{F}$ (or vice versa), $xz\in L↓M=L↓{M'}$, $yz\not\in L↓M=L↓{M'}$,
so $S'\delta'↓x≠S'\delta'↓y$.

Let $x↓1,x↓2,\ldots,x↓k$ be such that each $S\delta↓{x↓i}$ represents a
distinct equivalence class; then $S'\delta'↓{x↓i}$ must all be distinct,
and $M'$ must have at least as many states as~$M↑{[\,]}$.
[The above argument does not consider reachability of states from~$S$, but
assumes all reachable. Drop unreachable states somewhere.]
[RWF: rewrite]

If $S\delta↓x≡S\delta↓y$, then $S\delta↓{xz}≡S\delta↓{yz}$, 
$xz\in L↓M$ iff $yz\in L↓M$,
and $x\sim y$. Conversely, if $x\sim y$, then $L↓{S\delta↓x}=L↓{S\delta↓y}$, so
$S\delta↓x≡S\delta↓y$. In a minimized machine~$M↑{[\,]}$, states are equivalent
only if equal, so $x\sim y$ iff $S↑{[\,]}\delta↓x↑{[\,]}=S↑{[\,]}\delta↓y↑{[\,]}$.
We conclude that the number of equivalence classes of~`$\sim$' is the
number of equivalence classes of~$[\,]$, which is the number of states
in~$M↑{[\,]}$. 

\smallskip
\disleft 38pt::
{\bf Exercise:} Show any two minimized machines for the same language
are essentially the same. (Midterm?)

\bigskip\noindent
{\bf Eliminating Unreachable States.}

Let $M=(Q,S,F,\delta,\Sigma)$ be a~FA. Define $Q'=S\delta↓{\Sigma↑{\ast}}=
S\delta↓{\Sigma}↑{\,\ast}$, where $\delta↓{\Sigma}=\bigcup↓{a\in\Sigma}\delta↓a$.
Define $S'=S$, $F'=F\cap Q'$, $\delta'=\delta\cap(Q'\times Q')$,
$\Sigma'=\Sigma$. Show $M'$ is a~DFA if $M$~is, and that
$L↓{M'}=L↓M$.

\smallskip\noindent
{\bf Proof:} Since $\delta'$ is a restriction of~$\delta$, it is singlevalued.
If $q↓1\in Q'$, $\exists x$~such that $S\delta↓xq↓1$, so, letting
$q↓2=q↓1\delta↓a$, $S\delta↓{xa}q↓2$, $q↓2\in Q'$, $q↓1\delta↓a'q↓2$, 
and $\delta'↓aq$~is
defined and in~$Q'$
for all $a\in\Sigma$, $q\in Q'$. Clearly $q\delta'↓x$ is then
defined for all $x\in \Sigma↑{\ast}$, $q\in Q'$.

If $x\in L↓M$, $S\delta↓xq\in F$, $q\in Q'$, $q\in F'$, $S'\delta'↓xq$,
so $x\in L↓{M'}$. If $x\in L↓{M'}$, $S'\delta'↓xq$ and $q\in F'$,
$S\delta↓xq$ and $q\in F$, so $x\in L↓M$.

In an NFA, because of the time symmetry, we may also eliminate states
from which no accepting state can be reached, by virtually the same
algorithm and proof. A~DFA, however, may need a `dead state' from which
no accepting state is reachable.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft November 14, 1984

\bye